package StackOrQueue;//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
//
// 整数除法仅保留整数部分。
//
//
//
//
//
// 示例 1：
//
//
//输入：s = "3+2*2"
//输出：7
//
//
// 示例 2：
//
//
//输入：s = " 3/2 "
//输出：1
//
//
// 示例 3：
//
//
//输入：s = " 3+5 / 2 "
//输出：5
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 3 * 10⁵
// s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
// s 表示一个 有效表达式
// 表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内
// 题目数据保证答案是一个 32-bit 整数
//
//
//
// Related Topics 栈 数学 字符串 👍 489 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class calculateII {
    static Map<Character, Integer> map = new HashMap<Character, Integer>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};
    static Stack<Character> helper = new Stack<>();
    static Stack<Integer> stack = new Stack<>();
    static void eval(){
        Integer op2 = stack.pop();
        Integer op1 = stack.pop();
        Character pop = helper.pop();
        if (pop == '*') {
            stack.push(op1 * op2);
        } else if (pop == '/') {
            stack.push(op1 / op2);
        } else if (pop == '+') {
            stack.push(op1 + op2);
        } else {
            stack.push(op1 - op2);
        }
    }

    public static int calculate(String s) {
        // 使用 map 维护一个运算符优先级
        // 这里的优先级划分按照「数学」进行划分即可

        /**
         * 双栈
         * 考虑 * / 的优先级大于 + -
         * 遇到加减先放入辅助栈，若下一个字符是非* / 则可以计算加减
         * */

        //中间空格去掉
        s = s.replace(" ", "");
        char[] chars = s.toCharArray();
        int len = s.length();
        int left = 0, right = 0;
        //双指针 识别中间的长数字字符串和运算符
        while (right < len) {
            //找到第一个不为运算符的位置
            while (right < len && !Character.isDigit(chars[right])) {
                right++;
            }
            left = right;
            //找到第一个运算符的位置
            while (right < len && Character.isDigit(chars[right])) {
                right++;
            }
            // 截取数字
            String number = s.substring(left, right);
            int i = Integer.parseInt(number);
            stack.push(i);   //数字入栈

            //当移动到最后时 right==len，此时无运算符
            if (right < len) {
                char operation = chars[right];
                /**
                 * 当当前操作符的优先级小于等于辅助栈顶时，计算辅助栈里的该操作
                 * 否则入栈
                 * */
                while (!helper.isEmpty() && map.get(operation) <= map.get(helper.peek())) {
                    eval();
                }
                helper.push(operation);  //操作符入辅助栈
            }
        }
        // 最后看是否还有运算符未处理
        while (!helper.isEmpty()) {
            eval();
        }
        return stack.pop();
    }

    public int calculate1(String s) {
        /**
         * 单栈
         * 遇到+ - 运算符,就把它后面的数字带符号存进去
         * 比如 +1-2，就入栈+1 和 -2
         * 遇到* /就出栈顶和运算符后的数字进行运算再入栈
         * 最后把栈内元素全部相加即可
         * */
        Deque<Integer> stack = new LinkedList<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
